//实现一个 MapSum 类，支持两个方法，insert 和 sum： 
//
// 
// MapSum() 初始化 MapSum 对象 
// void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 
//key 已经存在，那么原来的键值对将被替代成新的键值对。 
// int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。 
// 
//
// 
//
// 示例： 
//
// 
//输入：
//inputs = ["MapSum", "insert", "sum", "insert", "sum"]
//inputs = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
//输出：
//[null, null, 3, null, 5]
//
//解释：
//MapSum mapSum = new MapSum();
//mapSum.insert("apple", 3);  
//mapSum.sum("ap");           // return 3 (apple = 3)
//mapSum.insert("app", 2);    
//mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)
// 
//
// 
//
// 提示： 
//
// 
// 1 <= key.length, prefix.length <= 50 
// key 和 prefix 仅由小写英文字母组成 
// 1 <= val <= 1000 
// 最多调用 50 次 insert 和 sum 
// 
//
// 
//
// 
// 注意：本题与主站 677 题相同： https://leetcode-cn.com/problems/map-sum-pairs/ 
//
// Related Topics 设计 字典树 哈希表 字符串 👍 32 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-02-27 09:03:13
 * @description LCR 066. 键值映射
 
 */
 
public class Z1R5dt {
    public static void main(String[] args) {
    //测试代码
    Z1R5dt fun = new Z1R5dt();

    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class MapSum {
    Trie p;
    /** Initialize your data structure here. */
    public MapSum() {
        p=new Trie();
    }
    
    public void insert(String key, int val) {
        p.insert(key,val);
    }
    
    public int sum(String prefix) {
        return p.searchPrefix(prefix);
    }
    class Trie{
        Trie [] ne;
        int val;
        Trie(){
            ne=new  Trie[26];
            val=0;
        }
        void insert(String key,int val){
            Trie p=this;
            for (char c : key.toCharArray()) {
                int ind=c-'a';
                if(p.ne[ind]==null){
                    p.ne[ind]=new Trie();
                }
                p=p.ne[ind];
            }
            p.val=val;
        }
        int searchPrefix(String prefix){
            Trie p=this;

            for (char c : prefix.toCharArray()) {
                int ind=c-'a';
                if(p.ne[ind]==null){
                   return 0;
                }
                p=p.ne[ind];
            }
            return sum(p);
        }

        public int sum(Trie trie) {
            if(trie==null) return 0;
            int res=trie.val;
            for (int i = 0; i < 26; i++) {
                if(trie.ne[i]!=null)
                res+=sum(trie.ne[i]);
            }
            return res;
        }
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
